170. Two Sum III - Data structure design
Easy

Design a data structure that accepts a stream of integers and checks if it has a pair of integers that sum up to a particular value.

Implement the TwoSum class:

  • TwoSum() Initializes the TwoSum object, with an empty array initially.
  • void add(int number) Adds number to the data structure.
  • boolean find(int value) Returns true if there exists any pair of numbers whose sum is equal to value, otherwise, it returns false.

 

Example 1:

Input
["TwoSum", "add", "add", "add", "find", "find"]
[[], [1], [3], [5], [4], [7]]
Output
[null, null, null, null, true, false]

Explanation
TwoSum twoSum = new TwoSum();
twoSum.add(1);   // [] --> [1]
twoSum.add(3);   // [1] --> [1,3]
twoSum.add(5);   // [1,3] --> [1,3,5]
twoSum.find(4);  // 1 + 3 = 4, return true
twoSum.find(7);  // No two integers sum up to 7, return false

 

Constraints:

  • -105 <= number <= 105
  • -231 <= value <= 231 - 1
  • At most 5 * 104 calls will be made to add and find.
Accepted
102,888
Submissions
291,693
Seen this question in a real interview before?
Companies
Related Topics

Average Rating: 4.72 (18 votes)

Premium

Solution


Approach 1: Sorted List

Intuition

First of all, the problem description is not terribly clear on the requirements of time and space complexity. But let us consider this as part of the challenge or a freedom of design. We could figure out the desired complexity for each function, by trial and error.

This is one of the followup problems to the first programming problem on LeetCode called Two Sum, where one is asked to return the indice of two numbers from a list that could sum up to a given value.

Let us take the inspiration from the origin problem, by keeping all the incoming numbers in a list.

Given a list, one of the solutions to the Two Sum problem is called Two-Pointers Iteration where we iterate through the list from two directions with two pointers approaching each other.

pic

However, one of the preconditions for the Two-Pointers Iteration solution is that the input list should be sorted.

So now, here are the questions:

  • Should we keep the list in order while inserting new numbers in the function add(number) ?

  • Or should we do the sorting on demand, i.e. at the invocation of find(value) ?

We will address the above two questions later in the Algorithm section.

Algorithm

Let us first give the algorithm of Two-Pointers Iteration to find the two-sum solution from a sorted list:

  • We initialize two pointers low and high which point to the head and the tail elements of the list respectively.

  • With the two pointers, we start a loop to iterate the list. The loop would terminate either we find the two-sum solution or the two pointers meet each other.

  • Within the loop, at each step, we would move either of the pointers, according to different conditions:

    • If the sum of the elements pointed by the current pointers is less than the desired value, then we should try to increase the sum to meet the desired value, i.e. we should move the low pointer forwards to have a larger value.

    • Similarly if the sum of the elements pointed by the current pointers is greater than the desired value, we then should try to reduce the sum by moving the high pointer towards the low pointer.

    • If the sum happen to the desired value, then we could simply do an early return of the function.

  • If the loop is terminated at the case where the two pointers meet each other, then we can be sure that there is no solution to the desired value.

The usage pattern of the desired data structure in the online judge, as we would discover, is that the add(number) function would be called frequently which might be followed a less frequent call of find(value) function.

The usage pattern implies that we should try to minimize the cost of add(number) function. As a result, we sort the list within the find(value) function instead of the add(number) function.

So to the above questions about where to place the sort operation, actually both options are valid and correct. Due to the usage pattern of the two functions though, it is less optimal to sort the list at each add operation.

On the other hand, we do not do sorting at each occasion of find(value) neither. But rather, we sort on demand, i.e. only when the list is updated. As a result, we amortize the cost of the sorting over the time. And this is the optimization trick for the solution to pass the online judge.

Complexity Analysis

  • Time Complexity:

    • For the add(number) function: O(1)\mathcal{O}(1), since we simply append the element into the list.

    • For the find(value) function: O(Nlog(N))\mathcal{O}(N \cdot \log(N)). In the worst case, we would need to sort the list first, which is of O(Nlog(N))\mathcal{O}(N \cdot \log(N)) time complexity normally. And later, again in the worst case we need to iterate through the entire list, which is of O(N)\mathcal{O}(N) time complexity. As a result, the overall time complexity of the function lies on O(Nlog(N))\mathcal{O}(N \cdot \log(N)) of the sorting operation, which dominates over the later iteration part.

  • Space Complexity: the overall space complexity of the data structure is O(N)\mathcal{O}(N) where NN is the total number of numbers that have been added.


Approach 2: HashTable

Intuition

As an alternative solution to the original Two Sum problem, one could employ the HashTable to index each number.

Given a desired sum value S, for each number a, we just need to verify if there exists a complement number (S-a) in the table.

As we know, the data structure of hashtable could offer us a quick lookup as well as insertion operations, which fits well with the above requirements.

Algorithm

  • First, we initialize a hashtable container in our data structure.

  • For the add(number) function, we build a frequency hashtable with the number as key and the frequency of the number as the value in the table.

  • For the find(value) function, we then iterate through the hashtable over the keys. For each key (number), we check if there exists a complement (value - number) in the table. If so, we could terminate the loop and return the result.

  • In a particular case, where the number and its complement are equal, we then need to check if there exists at least two copies of the number in the table.

We illustrate the algorithm in the following figure:

pic

Complexity Analysis

  • Time Complexity:

    • For the add(number) function: O(1)\mathcal{O}(1), since it takes a constant time to update an entry in hashtable.

    • For the find(value) function: O(N)\mathcal{O}(N), where NN is the total number of unique numbers. In the worst case, we would iterate through the entire table.

  • Space Complexity: O(N)\mathcal{O}(N), where NN is the total number of unique numbers that we will see during the usage of the data structure.

Report Article Issue

Comments: 17
byronshilly's avatar
Read More

Isn't the time complexity for Approach 2's find function linear? Looking up the compliment is done in constant time, but in the event that no valid pair exists, the algorithm will loop through the entire hash table looking for compliments.

17
Show 2 replies
Reply
Share
Report
robinali34's avatar
Read More

The HashMap solutions is hard to read, modified a bit:

class TwoSum {
    private HashMap<Integer, Integer> num_counts;

    /** Initialize your data structure here. */
    public TwoSum() {
        this.num_counts = new HashMap<>();
    }
    
    /** Add the number to an internal data structure.. */
    public void add(int number) {
        this.num_counts.put(number, num_counts.getOrDefault(number, 0) + 1);
    }
    
    /** Find if there exists any pair of numbers which sum is equal to the value. */
    public boolean find(int value) {
        for(Integer key : this.num_counts.keySet()) {
            int complement = value - key;
            if(complement != key) {
                if(this.num_counts.containsKey(complement))
                    return true;
            } else if(this.num_counts.get(key) > 1)
                return true;
        }
        return false;
    }
}

13
Reply
Share
Report
hiepit's avatar
Read More

Is the constraint of this problem correct? If add takes O(1) and time takes O(N). Then if I add 2*10^4 different numbers and find 3*10^4 times then TLE will occur.
Discussion topic: https://leetcode.com/problems/two-sum-iii-data-structure-design/discuss/884946/The-constraint-is-WRONG

5
Show 2 replies
Reply
Share
Report
Ayamin's avatar
Read More

I think we can get linear add() and constant time find(), if we keep a Set of all the sums.
When we add, compute the pair-wise sum of the new element with all the existing elements, and add those pair-wise sums to the set.

Just something to consider, depending on the behavior in traffic on those 2 API endpoints of this class ;)

Edit: I'm getting TLE with this implementation. It looks like there are more calls to add() than find() in the test cases.

4
Show 5 replies
Reply
Share
Report
noobiedoobie's avatar
Read More

In the first solution the author forgot to do self.is_sorted = True at line 37.

2
Show 3 replies
Reply
Share
Report
undefitied's avatar
Read More

You can do sorted array in O(n) time, if you will maintain it with each addition.
Then add(number) -> O(n)
and find(value) -> O(n)
Space for the sorted array O(number of unique items)

2
Show 1 reply
Reply
Share
Report
GodStaffJax's avatar
Read More

This Leetcode question is useless. Basically, we solve the problem using Two Sum or Two Sum II. The streaming thing does not add value at all.

0
Reply
Share
Report
leeterman's avatar
Read More

Will the Two-Pointer solution work when negative numbers are part of the list (allowed as per problem statement)?

Lets say we maintain the list as sorted, and we are asked to find(-8) when the list currently looks like this:
[-5,-4,-3,-2,-1]

Clearly, there is a solution (-8 == -5 + -3).
But the algorithm, as detailed above, would work as per the table below and declare no success.

Iter | Low | High | Sum | TwoSum |
-----+-----+------+-----+--------|
  0  |  0  |  4   | -6  |   -8   | 
  1  |  1  |  4   | -5  |   -8   |
  2  |  2  |  4   | -4  |   -8   |
  3  |  3  |  4   | -3  |   -8   |
  4  |  4  |  4   | FAIL|   -8   |

0
Show 1 reply
Reply
Share
Report
suganya-sk's avatar
Read More

Isn't the time complexity for Approach:2's 'find' O(n^2) since looking up each complement will also involve iterating through the whole data structure? Can someone explain please? Thanks in advance!

0
Show 1 reply
Reply
Share
Report
ardalanb's avatar
Read More

class TwoSum(object):

def __init__(self):
    self.nums = []
    

def add(self, number):
    """
    Add the number to an internal data structure..
    :type number: int
    :rtype: None
    """
    number = self.nums.append(number)
    

def find(self, value):
    """
    Find if there exists any pair of numbers which sum is equal to the value.
    :type value: int
    :rtype: bool
    """
    numbers = self.nums
    seen = set()
    
    for i, num in enumerate(numbers):
        rem = value - num
        if rem not in seen:
            seen.add(num)
        else:
            return True
        
    return False

Your TwoSum object will be instantiated and called as such:

obj = TwoSum()

obj.add(number)

param_2 = obj.find(value)

0
Show 1 reply
Reply
Share
Report
Success
Details
Runtime: 152 ms, faster than 50.13% of C++ online submissions for Two Sum III - Data structure design.
Memory Usage: 24.7 MB, less than 15.76% of C++ online submissions for Two Sum III - Data structure design.
Next challenges:
Time Submitted
Status
Runtime
Memory
Language
06/19/2021 08:39Accepted152 ms24.7 MBcpp
06/19/2021 08:39Runtime ErrorN/AN/Acpp
/23
Contribute
|||
Saved
Trie
This list is empty.